<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- K 次调整数组大小浪费的最小总空间 -->
    <script>
      /*
        思路：定义状态： dp[i][j]表示[0, i]区间分成j段，最小的浪费空间；
              状态的初始条件:
                任何长度为i的区间，最多只能被分成i段，因此任何j > i + 1的dp元素，都非法，应设为Infinity；
                任何长度为i的区间，如果被分成i段，那么可以完美贴合当前区间的所有值，没有浪费空间，因此dp[i][i+1] = 0。
      */
      var minSpaceWastedKResizing = function (nums, k) {
        // dp[i][j]: [0, i]区间分成j份，最小的浪费空间。
        let dp = new Array(nums.length).fill(0).map(i => new Array(k + 2).fill(0))
        let g = new Array(nums.length).fill(0).map(i => new Array(nums.length).fill(0)) // 保存[i,j]区间的空位数
        for (let i = 0; i < nums.length; i++) {
          let max = -Infinity
          let sum = 0
          for (let j = i; j < nums.length; j++) {
            sum += nums[j]
            max = Math.max(max, nums[j])
            g[i][j] = (j - i + 1) * max - sum
          }
        }
        for (let i = 0; i < dp.length; i++) {
          for (let j = 1; j < dp[0].length; j++) {
            let min = Infinity
            for (let t = i; t >= 0; t--) {
              let cur
              if (t - 1 < 0) cur = j - 1 === 0 ? 0 : Infinity
              else cur = j - 1 === 0 ? Infinity : dp[t - 1][j - 1]
              min = Math.min(cur + g[t][i], min)
            }
            dp[i][j] = min
          }
        }
        return dp[nums.length - 1][k + 1]
      }
      console.log(minSpaceWastedKResizing([10, 20], 0))
    </script>
  </body>
</html>
